package com.bo.day20241121;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 图的宽度优先遍历
 *
 * @Author: gpb
 * @Date: 2024/11/22 14:45
 * @Description:
 */
public class BFS {
    /**
     * 图宽度优先遍历
     * 思路：
     * 1.创建一个队列，将起始节点放入队列中
     * 2.从队列中取出节点，访问节点，将节点的邻接节点放入队列中，直到队列为空
     *
     * @param node
     */
    public static void bfs (Node node) {
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        Set<Node> set = new HashSet<>();
        queue.add(node);
        set.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.value + " ");
            for (Node nest : cur.nexts) {
                if (!set.contains(nest)) {
                    queue.add(nest);
                    set.add(nest);
                }
            }
        }
    }
}
